// https://leetcode.cn/problems/number-of-enclaves/description/

// 算法思路总结：
// 1. 从边界陆地开始广度优先搜索标记可到达的陆地
// 2. 使用队列处理所有边界连通陆地区域
// 3. 将可达陆地标记为特殊值避免重复访问
// 4. 最后统计未被标记的陆地数量即为飞地数量
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

class Solution 
{
public:
    int m, n;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    typedef pair<int, int> PII;

    int numEnclaves(vector<vector<int>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        queue<PII> q;

        for (int i = 0 ; i < m ; i++)
        {
            for (int j =  0 ; j < n ; j++)
            {
                if (grid[i][j] == 1 && (i == 0 || j == 0 || i == m - 1 || j == n - 1))
                {
                    q.push({i, j});
                    grid[i][j] = 2;
                }
            }
        }

        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();

            for (int i = 0 ; i < 4 ; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == 1)
                {
                    q.push({x, y});
                    grid[x][y] = 2;
                }
            }
        }

        int ret = 0;
        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (grid[i][j] == 1)
                {
                    ret++;
                }
            }
        }

        return ret;
    }
};

int main()
{
    vector<vector<int>> grid1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
    vector<vector<int>> grid2 = {{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}};
    Solution sol;

    cout << sol.numEnclaves(grid1) << endl;
    cout << sol.numEnclaves(grid2) << endl;

    return 0;
}